 %!TEX program = xelatex
\documentclass[lang=cn,10pt]{elegantbook}

% 本文档命令
\usepackage{array,url}
\newcommand{\ccr}[1]{\makecell{{\color{#1}\rule{1cm}{1cm}}}}
\newcommand{\code}[1]{\lstinline{#1}}


% 文档区
\begin{document}

\chapter*{数值分析作业--Week2}

\begin{problem}
对$f\in\mathcal{C}^2[x_0,x_1]$与$x\in(x_0,x_1)$，$f$在$x_0,x_1$的线性插值满足
\[f(x)-p_1(f;x)=\dfrac{f''(\xi(x))}{2}(x-x_0)(x-x_1)\]
考虑$f(x)=\dfrac{1}{x},x_0=1,x_1=2$
\begin{itemize}
    \item 给出$\xi(x)$
    \item 将$\xi$定义域连续延拓到$[x_0,x_1]$上，求$\max{\xi(x)},\min{\xi(x)},\max{f''(\xi(x))}$
\end{itemize}
\end{problem}
\begin{proof}
(1)
我们熟知当
\[p_1(f;x)=a_0+a_1x^2\]
有
\[\left(\begin{array}{c}
a_0\\ a_1 \\
\end{array}\right)\left(
\begin{array}{cc}
1  & x_0\\ 1 & x_1 \\
\end{array}\right)\left(
=\begin{array}{c}
f(x_0)\\ f(x_1) \\
\end{array}\right)
\]
解得
\[\begin{cases} a_0 = \dfrac{f(x_1)x_0-f(x_0)x_1}{x_0-x_1} \\ a_1 = \dfrac{f(x_0)-f(x_1)}{x_0-x_1}\end{cases}\]
求得
\[f''(\xi(x))=\dfrac{2[f(x)-\dfrac{f(x_0)-f(x_1)}{x_0-x_1}-x\dfrac{f(x_1)x_0-f(x_0)x_1}{x_0-x_1}]}{(x-x_0)(x-x_1)}\]
对于$f(x)=\dfrac{1}{x}$，有$f''(x)=\dfrac{2}{x^3}$，对于$\xi:\mathbb{R}\to\mathbb{R}$有
\[\xi(x)=(2x)^{\tfrac{1}{3}}\]
从而$\xi(x)$关于$x$在$[1,2]$单调递增，可得
\[\min{\xi(x)}=\xi(1)=2^{\tfrac{1}{3}}\quad \max{\xi(x)}=4^{\tfrac{1}{3}}\]
又\[f''(\xi(x)) = \dfrac{2}{\xi(x)^3}\]由于$\xi(x)$不变号，则$f''(\xi(x))$在$[1,2]$单调递减，故\[\max{f''(\xi(x))} = f''(\xi(1)) = 1\]
综上所述
\[\min{\xi(x)}=2^{\tfrac{1}{3}}\quad \max{\xi(x)}=4^{\tfrac{1}{3}} \quad \max{f''(\xi(x))} = 1\]
\end{proof}
\vspace{1.5em}
\begin{problem}
令$\mathbb{P}_m^+$是所有次数小于等于$m$并且在实轴上非负的多项式的集合，求$p\in\mathbb{P}_{2n}^+$使得$p(x_i)=f_i$对$i=0,1,\cdots,n$成立，其中$f_i\geq 0 $并且$x_i$两两不同
\end{problem}
\begin{proof}
考虑对$x_i, 0\leq i \leq n$与$f(x_i)=\sqrt{f_i}$的插值多项式$p_n(f;x)$，我们熟知$p_n(f;x)$存在且唯一，则令$p_{2n}(x) = p_n(f;x)^2$，显然$p_{2n}(x_i) = f_i$并且在实轴非负，满足条件，故$p_{2n}(x)$即为所求
\end{proof}
\vspace{1.5em}
\begin{problem}
考虑$f(x)=e^x$
\begin{itemize}
    \item 用归纳法证明
    \[\forall t\in\mathbb{R}\quad f[t,t+1,\cdot,t+n]=\dfrac{(e-1)^n}{n!}e^t\]
    \item 我们熟知
    \[\exists \xi\in(0,n)\ s.t.\ f[0,1,\cdots,n]=\dfrac{1}{n!}f^{(n)}(\xi)\]
    从上述两个等式求解$\xi$，并说明$\xi$在$\tfrac{n}{2}$的左侧还是右侧
\end{itemize}
\end{problem}
\begin{proof}
(1)$n=0$，原式为
\[f[t] = e^t\]显然成立，下面证明$P(n=k)\implies P(n=k+1)$，我们熟知
\[\begin{aligned}f[t,t+1,\cdots,t+k+1]&=\dfrac{f[t+1,t+2,\cdots,t+k+1]-f[t,t+1,\cdots,t+k]}{k+1} \\ &= \dfrac{1}{k+1}(\dfrac{(e-1)^k}{k!}e^{t+1}-\dfrac{(e-1)^k}{k!}e^{t})\\
&=\dfrac{(e-1)^{k+1}}{(k+1)!}e^t\end{aligned}\]
即证\par
(2)根据上问结论
\[f[0,1,\cdots,n] = \dfrac{(e-1)^n}{n!} \]
又有
\[f[0,1,\cdots,n] = \dfrac{1}{n!}f^{(n)}(\xi) = \dfrac{1}{n!}e^{\xi}\]
从而$\xi = n\ln(e-1)$，有
\[\dfrac{\xi}{\tfrac{n}{2} = 2\ln(e-1)}\]
注意到
\[(e-1)^2 -e = (e-\dfrac{3}{2})^2-\dfrac{5}{4} > 0 \]
故$2\ln(e-1)>1$，有$\xi > \dfrac{n}{2}$，这说明$\xi$ 在$\dfrac{n}{2}$的右边
\end{proof}
\vspace{1.5em}

\begin{problem}
考虑$f(0)=5,f(1)=3,f(3)=5,f(4)=12$
\begin{itemize}
    \item 用牛顿公式给出$p_3(f;x)$
    \item 数据说明$f$在$(1,3)$可以取到极小值，给出极小点的一个估计
\end{itemize}
\end{problem}
\begin{proof}
(1)根据牛顿插值公式有
\[\begin{aligned} p_3(f;x) &= f(0) + f[0,1]x + f[0,1,3]x(x-1) + f[0,1,3,4]x(x-1)(x-3) \\ & = \dfrac{1}{4}x(x-1)(x-3) + x(x-1) -2x +5 \end{aligned}\]
(2)对$p_3(f;x)$关于$x$求导有
\[p_3'(f;x) = \dfrac{3}{4}(x^2-3) \]
故可给出$(1,3)$间极小点的估计为$\sqrt{3}$
\end{proof}
\vspace{1.5em}

\begin{problem}
考虑$f(x)=x^7$
\begin{itemize}
    \item 计算$f[0,1,1,1,2,2]$
    \item 差商可以表达为$f$的$5$阶导数在$\xi\in(0,2)$的值，求$\xi$
\end{itemize}
\end{problem}
\begin{proof}
(1)根据差商表计算可得
\[f[0,1,1,1,2,2] = 30\]
(2)
\[f[0,1,1,1,2,2] = \dfrac{f^{(5)}(\xi)}{5!} = \dfrac{7!\xi^2}{2!5!} \implies \xi = \dfrac{\sqrt{70}}{7}\]
\end{proof}
\vspace{1.5em}

\begin{problem}
$f$是$[0,3]$上的函数且
\[f(0)=1,f(1)=2,f'(1)=-1,f(3)=f'(3)=0\]
\begin{itemize}
    \item 用Heimite插值估计$f(2)$
    \item 给出上述估计的最大可能误差，前提是$f\in\mathcal{C}^5[0,3]$且$|f^{(5)}(x)|\leq M,\forall x\in[0,3]$，用含$M$的形式写出答案
\end{itemize}
\end{problem}
\begin{proof}
(1)根据Heimite插值公式，有
\[p_4(f;x) = f(0) + f[0,1]x + f[0,1,1]x(x-1) + f[0,1,1,3]x(x-1)^2 + f[0,1,1,3,3]x(x-1)^2(x-3)\]
根据差商表可以计算得
\[p_4(f;2) = \dfrac{11}{18}\]作为$f(2)$的估计\\
(2)
熟知
\[f(x)-p_4(f;x) = \dfrac{f^{(5)}(x)}{5!}x(x-1)^2(x-3)^2\]
从而
\[error = |f(2)-p_4(f;2)| = |\dfrac{2f^{(5)}(2)}{5!}| \leq \dfrac{M}{60}\]
上式当$f^{(5)}(2) = M$取等，故最大可能误差
\[error_{max} = \dfrac{M}{60}\]
\end{proof}
\vspace{1.5em}

\begin{problem}
定义前差分
\[\Delta f(x) = f(x+h)-f(x)\]
定义后差分
\[\nabla f(x) = f(x)-f(x-h)\]
证明
\[\begin{aligned}\Delta^kf(x)&=k!h^kf[x_0,x_1,\cdots,x_k] \\\nabla^kf(x)&=k!h^kf[x_0,x_{-1},\cdots,x_{-k}] \end{aligned}\]
其中$x_t = x + th, \forall t\in\mathbb{Z}$
\end{problem}
\begin{proof}
我们对$k$施用数学归纳法，当$k=1$时
\[\Delta f(x) = f(x+h)-f(x) = hf[x_0,x_1]\]
来证$P(k=m)\implies P(k=m+1)$有
\[\begin{aligned}
\Delta^{m+1}f(x) &= \Delta^m f(x+h) - \Delta^m f(x) \\ &= m!h^m(f[x_1,x_2,\cdots,x_{m+1}]-f[x_0,x_1,\cdots,x_m])\\ & = (m+1)!h^{m+1}f[x_0,x_1,\cdots,x_{m+1}]\end{aligned}\]
即证
\[\Delta^kf(x)=k!h^kf[x_0,x_1,\cdots,x_k]\]
而
\[\nabla^kf(x)=k!h^kf[x_0,x_{-1},\cdots,x_{-k}]\]
类似可证，不再赘述
\end{proof}
\vspace{1.5em}
\newpage 

\begin{problem}
(1)假设$f$在$x_0$可微，证明
\[\dfrac{\partial}{\partial x_0}f[x_0,x_1,\cdots,x_n] = f[x_0,x_0,x_1,\cdots,x_n]\]
讨论关于其他变量的偏导数
\end{problem}
\begin{proof}
事实上，左式可以看做是这个极限
\[\lim\limits_{\varepsilon\to 0}f[x_0,x_0+\varepsilon,x_1,\cdots,x_n]\]
与不等于$x_0$的$n$个变量$x_i,1\leq i\leq n$有关，我们证明上述极限存在并且等于
$f[x_0,x_0,x_1,\cdots,x_n]$
当与$x_0$无关的变量个数为$n$，这样可以对无关变量个数$n$施用数学归纳法，当$n=0$时，上式等价于
\[f'(x_0) = f[x_0,x_0]\]
根据$f$在$x_0$，上式成立，下面证明$P(n=k)\implies P(n=k+1)$，注意到
\[f[x_0,x_0+\varepsilon,x_1,\cdots,x_{k+1}]=\dfrac{f[x_0,x_0+\varepsilon,x_1,\cdots,x_{k}]-f[x_0,x_1,\cdots,x_{k+1}]}{x_{k+1}-(x_0+\varepsilon)}\]
根据归纳假设，其中右式关于$\varepsilon\to 0 $的极限存在，等于\[\dfrac{f[x_0,x_0,x_1,\cdots,x_{k}]-f[x_0,x_1,\cdots,x_{k+1}]}{x_{k+1}-x_0} = f[x_0,x_0,x_1,\cdots,x_{k+1}]\]
因此极限
\[\lim\limits_{\varepsilon\to 0}f[x_0,x_0+\varepsilon,x_1,\cdots,x_{k+1}]\]
存在且等于$f[x_0,x_0,\cdots,x_{k+1}]$，证毕\\
(2)根据上述讨论，若$f$对其他变量$x_i$也可微，则根据差商的交换不变性，也有相似结论
\end{proof}
\vspace{1.5em}

\begin{problem}
对于$n\in\mathbb{N}^+$和给定的$a_0$，求
\[\min\limits_{a_i\in\mathbb{R},1\leq i \leq n}{\max\limits_{x\in[a,b]}{|a_0x^n+a_1x^{n-1}+\cdots+a_n|}}\]
\end{problem}
\begin{proof}
令\[ x = \dfrac{a+b}{2}+\dfrac{b-a}{2}t\]
所求即变为
\[\min\limits_{a_i\in\mathbb{R},1\leq i \leq n}{\max\limits_{t\in[-1,1]}{|a_0(\dfrac{a+b}{2}+\dfrac{b-a}{2}t)^n+a_1(\dfrac{a+b}{2}+\dfrac{b-a}{2}t)^{n-1}+\cdots+a_n|}}=a_0(\dfrac{b-a}{2})^n\min\limits_{a_i\in\mathbb{R},1\leq i \leq n}{\max\limits_{t\in[-1,1]}{|P_{a_i}(t)|}}\]
其中$P_{a_i}(t)$是由$a_i,1\leq i\leq n$决定的首一多项式，容易知道$P_{a_i}(t)$可以取到所有$n$次首一多项式，于是原式变为\[a_0(\dfrac{b-a}{2})^n\min\limits_{P\in\mathbb{P}_n}{\max\limits_{t\in[-1,1]}{|P(t)|}}\]
根据Chebysshev定理可知
\[\max\limits_{t\in[-1,1]}{|P(t)|}\geq \dfrac{1}{2^{n-1}}\]
当取$P(x) = \dfrac{T(x)}{2^{n-1}}$时可以取等，因此有
\[\dfrac{a_0(b-a)^n}{2^{2n-1}}\]为所求
\end{proof}
\vspace{1.5em}

\begin{problem}
对一个给定的$a>1$，定义$\mathbb{P}_n^a:=\{p\in\mathbb{P_n}:p(a)=1\}$并且对于$\hat{p_n}(x)\in\mathbb{P}^a_n$令它有
\[\hat{p_n}(x):=\dfrac{T_n(x)}{T_n(a)}\]证明\[\forall p\in\mathbb{P}^a_n,\quad \max\limits_{x\in[-1,1]}{|\hat{p_n}(x)|} \leq \max\limits_{x\in[-1,1]}{|p(x)|} \]
\end{problem}
\begin{proof}
上式
\[\max\limits_{x\in[-1,1]}{|\dfrac{T_n(x)}{T_n(a)}|} \leq \max\limits_{x\in[-1,1]}{|p(x)|}\]
等价于
\[\max\limits_{x\in[-1,1]}{|T_n(x)|} \leq \max\limits_{x\in[-1,1]}{|T_n(a)p(x)|}\]
反证：假设结论不成立，考虑多项式
\[P_n(x) = T_n(x)-T_n(a)p(x)\]
我们熟知$T_n(x)$在$\cos{\dfrac{k}{n}\pi},0\leq k \leq n$取得极值$\cos{k\pi}=(-1)^k$，从而$P_n(x)$在$[-1,1]$存在$n$个不同零点，同时又知道$P(a)=0,a>1$，故$P$有$n+1$不同零点，因此$P$恒为0，有$p(x)=\hat{p_n}(x)$，矛盾，综上，结论成立
\end{proof}
\vspace{1.5em}

\begin{problem}
证明引理2.50
\end{problem}
\begin{proof}
(a)是平凡的\\
(b)有
\[\sum\limits_{k=0}^n b_{n,k}(t) = \sum\limits_{k=0}^n C_n^kt^k(1-t)^{n-k} = [t+(1-t)]^n = 1\]
(c)有
\[\sum\limits_{k=0}^n kb_{n,k}(t) = nt \sum\limits_{k=0}^n C_{n-1}^{k-1} t^{k-1}(1-t)^{n-k} = nt[t+(1-t)]^{n-1} = nt\]
(d)有
\[\begin{aligned}
\sum\limits_{k=0}^n (k-nt)^2b_{n,k}(t)
&=\sum\limits_{k=0}^n k(k-1)b_{n,k}(t) +(1-2nt)\sum\limits_{k=0}^n kb_{n,k}(t) +n^2t^2\sum\limits_{k=0}^n b_{n,k}(t) \\ 
&= n(n-1)t^2 \sum\limits_{k=0}^n C_{n-2}^{k-2} t^{k-2}(1-t)^{n-k} + nt-n^2t^2 \\
&= n(n-1)t^2[t+(1-t)]^{n-2} + nt(1-nt) = nt(1-t)
\end{aligned}\]
证毕

\end{proof}
\end{document}
